
//739.每日温度
class Solution {
public:
    vector<int> dailyTemperatures(vector<int>& nums) {
        //从左向右,维护还没有找到答案的位置
        int n=nums.size();
        stack<pair<int,int>> st;
        st.push({nums[0],0});

        vector<int> ret(n,0);
        for(int i=1;i<n;i++)
        {
            while(!st.empty()&&nums[i]>st.top().first)  //如果nums[i]>top的值,说栈顶的元素找到答案了
            {
                int index=st.top().second;
                ret[index]=i-index;
                st.pop();
            }

            st.push({nums[i],i});  //将当前位置加入栈
        }
        return ret;
    }
};